// 给定两个数组 nums1 和 nums2 ，返回 它们的 交集 。输出结果中的每个元素一定是 唯一 的。我们可以 不考虑输出结果的顺序 。

// 思路1，双指针法，先排序，然后用两个指针分别遍历数组，判断是否相同

function intersection(arr1, arr2) {
    arr1.sort((a, b) => a - b)
    arr2.sort((a, b) => a - b)
    let index1 = 0
    let index2 = 0
    let ans = []
    while (index1 < arr1.length && index2 < arr2.length) {
        if (arr1[index1] === arr2[index2]) {
            !ans.includes(arr1[index1]) && ans.push(arr1[index1])
            index1++
            index2++
        } else if (arr1[index1] > arr2[index2]) {
            index2++
        } else {
            index1++
        }
    }
    return ans
}

let arr1 = [4, 9, 5]
let arr2 = [9, 4, 9, 8, 4]
console.log(intersection(arr1, arr2));

// 思路2，哈希表法，找出较短的数组，构造set，然后遍历另一个数组，判断相同的元素

function intersection2(arr1, arr2) {
    if (arr1 > arr2) {
        intersection(arr2, arr1)
    }
    const ans = []
    const set = new Set(arr1)
    const resSet = new Set()
    for (const item of arr2) {
        if (set.has(item)) {
            resSet.add(item)
            
        }
    }
    return Array.from(resSet)
}

let arr11 = [4, 9, 5]
let arr22 = [9, 4, 9, 8, 4]
console.log(intersection2(arr11, arr22));